
#include <stdio.h>

void Shell(int* a, int n)
{
  int gap = n;

  while(gap > 1)
  {
    gap = gap / 3 + 1;
    //保证gap的最后一次结果是1
    
    int i;
    for(i = 0; i < n-gap; ++i)
    {
      int end = i;
      int tmp = a[end+gap];

      while(end >= 0)
      {
        if(tmp < a[end])
        {
          //大的向后走
          a[end+gap] = a[end];
          end -= gap;
        }
        else
        {
          break;
        }
      }
      //小的向前走，或者是不动
      a[end+gap] = tmp;
    }
  }
}

void Test()
{
  int arr[] = {-1,-2,3,10,7,6,4,2,3,1,1,30};
  int sz = sizeof(arr) / sizeof(arr[0]);

  Shell(arr, sz);

  int i = 0;
  for(i = 0; i < sz; ++i)
  {
    printf("%d ", arr[i]);
  }
  printf("\n");
}

int main()
{
  Test();
  return 0;
}
